package com.lisp.algorithm.test.sort;

public class Median {

	public static void main(String[] args) {
		int a[] = {8, 12, 18};
		int b[] = {10};
		
		int totalLen = a.length + b.length;
		if(totalLen % 2 == 0) {
			System.out.println(kth(a, 0, b, 0, totalLen/2));
			System.out.println(kth(a, 0, b, 0, totalLen/2 + 1));
		} else {
			System.out.println(kth(a, 0, b, 0, totalLen/2+1));
		}
	}
	
	private static int kth(int a[], int aStart, int b[], int bStart, int k) {
		if(aStart > a.length-1) {
			System.out.println("----b[" + (bStart+k-1) + "]");
			return b[bStart + k - 1];
		} else if(bStart > b.length - 1) {
			System.out.println("----a[" + (aStart+k-1) + "]");
			return a[aStart + k - 1];
		}
		
		if(k == 1) {
			System.out.println("----" + aStart + " " + bStart);
			return Math.min(a[aStart], b[bStart]);
		}
		
		int halfK = k/2;
		if(aStart + halfK >= a.length) {
			int aLast = a[a.length-1];
			if(aLast < b[bStart + halfK]) {
				return kth(a, a.length, b, bStart, k-(a.length-aStart));
			} else {
				return kth(a, aStart, b, bStart+halfK, k-halfK);
			}
		} else if(bStart + halfK >= b.length) {
			int bLast = b[b.length-1];
			if(bLast < a[aStart+halfK]) {
				return kth(a, aStart, b, b.length, k-(b.length-bStart));
			} else {
				return kth(a, aStart+halfK, b, bStart, k-halfK);
			}
		} else {
			if(a[aStart+halfK] < b[bStart+halfK]) {
				return kth(a, aStart+halfK, b, bStart, k-halfK);
			} else {
				return kth(a, aStart, b, bStart+halfK, k-halfK);
			}
		}
	}
}
